package com.leetcode.partition3;

import java.util.Arrays;

/**
 * @author `RKC`
 * @date 2021/10/25 8:12
 */
public class LC240搜索二维矩阵2 {

    public static boolean searchMatrix(int[][] matrix, int target) {
//        return binarySearch(matrix, target);
        //Z字形查找，由于每行是升序、每列也是升序，如果matrix[i][j]>target，所有j列都是大于target，此时j--
        //如果matrix[i][j]<target，所有i行都是小于target，将i++
        int i = 0, j = matrix[0].length - 1;
        while (i < matrix.length && j >= 0) {
            if (matrix[i][j] == target) {
                return true;
            } else if (matrix[i][j] > target) {
                j--;
            } else {
                i++;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        int[][] matrix = {{1, 4, 7, 11, 15}, {2, 5, 8, 12, 19}, {3, 6, 9, 16, 22}, {10, 13, 14, 17, 24}, {18, 21, 23, 26, 30}};
        System.out.println(searchMatrix(matrix, 5));
    }

    private static boolean binarySearch(int[][] matrix, int target) {
        for (int i = 0; i < matrix.length; i++) {
            if (Arrays.binarySearch(matrix[i], target) >= 0) {
                return true;
            }
        }
        return false;
    }
}
